package com.yt.ds.chapter2;

import com.yt.ds.util.SortUtil;

/**
 * @Author: lzf
 * @Date: 2020/7/11 17:04
 * @Description: 归并排序
 */
public class MergeSort implements Sort {
    private Comparable[] aux;

    @Override
    public Comparable[] sort(Comparable[] array) {
        aux = new Comparable[array.length];
        sort(array, 0, array.length - 1);
        return array;
    }

    private void sort(Comparable[] array, int head, int tail) {
        if (head >= tail) {
            return;
        }
        int mid = head + (tail - head) / 2;
        sort(array, head, mid);
        sort(array, mid + 1, tail);
        merge(array, head, mid, tail);
    }

    /**
     * 合并: 将数组中两段有序部分，合并
     */
    private void merge(Comparable[] array, int head, int mid, int tail) {
        int left = head;
        int right = mid + 1;
        for (int i = head; i < tail + 1; i++) {
            aux[i] = array[i];
        }
        for (int i = head; i < tail + 1; i++) {
            if (left > mid) {
                array[i] = aux[right];
                right++;
            } else if (right > tail) {
                array[i] = aux[left];
                left++;
            } else if (SortUtil.less(aux, left, right)) {
                array[i] = aux[left];
                left++;
            } else {
                array[i] = aux[right];
                right++;
            }
        }
    }
}

